class node(object):
    '''
    节点类
    '''
    def __init__(self,elem=-1,lchild=None,rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild
class tree:
    def __init__(self):
        self.root=None#树根
        self.queue=[]#辅助队列
    def add_node(self,elem):
        new_node=node(elem)
        self.queue.append(new_node)#进队
        #判断树根是否为空
        if self.root==None:
            self.root=new_node
        else:
            if self.queue[0].lchild==None:#左孩子父亲为空，新节点为左孩子
                self.queue[0].lchild=new_node
            else:
                self.queue[0].rchild=new_node#父亲的孩子为空，新节点就作为左孩子
                self.queue.pop(0)#出队
    def pre_order(self,current_node:node):
        if current_node:
            print(current_node.elem,end=' ')
            self.pre_order(current_node.lchild)#遍历左子树
            self.pre_order(current_node.rchild)#遍历右子树
    def mid_order(self,current_node:node):#中序遍历
        if current_node:
            self.mid_order(current_node.lchild)  # 遍历左子树
            print(current_node.elem,end=' ')
            self.mid_order(current_node.rchild)#遍历右子树
    def last_order(self,current_node:node):#中序遍历
        if current_node:
            self.last_order(current_node.lchild)  # 遍历左子树
            self.last_order(current_node.rchild)#遍历右子树
            print(current_node.elem, end=' ')
    def level_order(self):
        node=self.root
        queue=[]
        queue.append(self.root)
        while queue:
            current_node=queue.pop(0)
            print(current_node.elem,end=' ')
            if current_node.lchild:
                queue.append(current_node.lchild)
            if current_node.rchild:
                queue.append(current_node.rchild)
if __name__=='__main__':
    tree=tree()
    for i in range(1,10):
        tree.add_node(i)
    tree.pre_order(tree.root)
    print("_"*100)
    tree.mid_order(tree.root)
    print("_"*100)
    tree.last_order(tree.root)
    print("_"*100)
    tree.level_order()